#include <iostream>
#include <vector>
#include <stack>

using namespace std;
// 42.接雨水
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
class Solution {
public:
    int trap(vector<int>& heights) {
        int ans = 0;
        for(int height : heights) {
            int accumulatedWidth = 0;   // 累加的宽度
            while(!s.empty() && s.top().height <= height) {
                int bottom = s.top().height;
                accumulatedWidth += s.top().width;
                s.pop();
                if(s.empty()) continue; // 水从左边流走了
                // 以bottom为底的横块水，最高可以到up(左右两侧的高度取最小值)
                int up = min(height,s.top().height);
                if(!s.empty() && s.top().height < up)
                    up = s.top().height;
                ans += accumulatedWidth * (up - bottom);
            }
            s.push({accumulatedWidth+1,height}); // 新的横条入栈
        }
        return ans;
    }

private:
    struct Rect {
        int width;
        int height;
    };
    stack<Rect> s;  // 定义一个单调栈
};

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
